package leetcode.graph.hamilton.p980;
/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.hamilton 
 * @Description: 980. 不同路径 III
 *                   自己的题解：不压缩二维数组的索引
 *                       改进：1、优化递归方法中的条件判断，避免重复判断二维数组的索引是否合法
 *                           2、基于v3将递归终止条件挪到for循环外面（由于递归更深了一层，性能并没有提升）
 * @author CandyWall   
 * @date 2021年1月19日 下午1:05:22 
 * @version V1.0
 */
class Solution_v4 {
    private int R;
    private int C;
    private int[][] grid;
    private boolean[][] visited;
    private int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        visited = new boolean[R][C];
        // 找出起始位置，并且统计空方格的个数
        int blank_count = 0;
        int firstI = 0;
        int firstJ = 0;
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(grid[i][j] == 1) {
                    firstI = i;
                    firstJ = j;
                } else if(grid[i][j] == 0) {
                    blank_count++;
                }
            }
        }
        // 起始方格也需要加入到未遍历的定点数中
        // 如果把递归终止条件放到循环外面（会多一次递归调用，left少减一次），
        // 最后的那个结束方格代表的顶点就也要算作未遍历的顶点
        // 因此起始方格和结束方格都要算在里面
        return dfs(firstI, firstJ, blank_count + 2);
    }
    
    private int dfs(int i, int j, int left) {
        left--;
        visited[i][j] = true;
        if(left == 0 && grid[i][j] == 2) {
            visited[i][j] = false;
            return 1;
        }
        int count = 0;
        for(int d = 0; d < 4; d++) {
            int nextI = dirs[d][0] + i;
            int nextJ = dirs[d][1] + j;
            // 如果把递归终止条件挪到for循环外面，
            // 需要把条件grid[nextI][nextJ] == 0改成grid[nextI][nextJ] != -1
            // 如果不改，最后当left == 1 && grid[nextI][nextJ] == 2的话就不能递归到下一层了，
            // 导致找不到正确的路径
            if(inArea(nextI, nextJ) && !visited[nextI][nextJ] && grid[nextI][nextJ] != -1) {
                count += dfs(nextI, nextJ, left);
            }
        }
        
        visited[i][j] = false;
        return count;
    }
    
    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution_v4().uniquePathsIII(new int[][] {{1,0,0,0}, {0,0,0,0}, {0,0,2,-1}}));
    }
}